package com.ljy.my_study.leetcode.组合;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lijunying
 * @date 2021/9/18 14:24
 */
public class TestMain {

//    给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
//
//    你可以按 任何顺序 返回答案。
//
//             
//
//    示例 1：
//
//    输入：n = 4, k = 2
//    输出：
//            [
//            [2,4],
//            [3,4],
//            [2,3],
//            [1,2],
//            [1,3],
//            [1,4],
//            ]
//    示例 2：
//
//    输入：n = 1, k = 1
//    输出：[[1]]
//             
//
//    提示：
//
//            1 <= n <= 20
//            1 <= k <= n
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/combinations
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        System.out.println(new TestMain().combine(3,2));
    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result=new ArrayList<>();
        dfs(n,k,1,new ArrayList<>(),result);
        return result;
    }

    private void dfs(int n,int k,int start,List<Integer> list,List<List<Integer>> result){
        int len=list.size();
        if(len==k){
            result.add(list);
            return;
        }
        for(int i=start;i<=(n-k+len+1);i++){
            List<Integer> newList=new ArrayList<>(list);
            newList.add(i);
            if(list.size()<k){
                dfs(n,k,i+1,newList,result);
            }
        }
    }
}
